/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  // 把数组转化成堆(列表转二叉树)
  // 树形结构可以用列表型的数组对象记录，也可以用树形的数组对象记录
  /* 
  
  列表型：
    整个 树就是一个数组，每一个节点是一个对象，这个对象要记录节点自身的特性（节点的值，和本节点在数组中对应元素的下标），还要记录此节点与其他节点之间的关系
          节点对象可以用value属性记录节点的值，index属性记录节点在数组中对应元素的下标
          节点之间是一对多的关系，用pInd(每一个节点对象都有一个pInd属性，记录节点的父元素在数组中的下标)来记录这种关系,堆顶元素的父元素的下标记为-1,父元素index*2+1=左子元素index(奇数),父元素index*2+2=右子元素index(偶数) */
  //   [{
  //     value: "5",
  //     index: "0",
  //     pInd: "-1"
  //   }, {
  //     value: "1",
  //     index: "1",
  //     pInd: "0"
  //   }, {
  //     value: "1",
  //     index: "2",
  //     pInd: "0"
  //   }, {
  //     value: "2",
  //     index: "3",
  //     pInd: "1"
  //   }, {
  //     value: "0",
  //     index: "4",
  //     pInd: "1"
  //   }, {
  //     value: "0",
  //     index: "5",
  //     pInd: "2"
  //   }]
  /* 
    树型：
      整个树是一个数组,每个节点是一个对象，这个对象要记录节点自身的特性（节点的值，和本节点在数组中对应元素的下标），还要记录此节点与其他节点之间的关系
          节点对象可以用value属性记录节点的值，index属性记录节点在数组中对应元素的下标，
          节点之间是一对多的关系，用children属性记录，children值是[],children中的每一项都是此节点的子节点对应的节点对象，子节点也有自己的子节点，也会放在自己的children属性数组中，最终就是一个树形结构
    */
  //   [{
  //     value: 5,
  //     index: 0,
  //     children: [{
  //       value: 1,
  //       index: 1,
  //       children: [{
  //         value: 2,
  //         index: 3,
  //         children: [{}]
  //       }, {
  //         value: 0,
  //         index: 4,
  //         children: [{}]
  //       }]
  //     }, {
  //       value: 1,
  //       index: 2,
  //       children: [{
  //         value: 0,
  //         index: 5,
  //         children: [{}]
  //       }]
  //     }]
  //   }]

  // 采用列表型数组对象存储堆
  //  const  tree= nums.reduce((result,item,index)=>{
  //     const obj ={}
  //       obj.value = item
  //       obj.index = index
  //       index===0?obj.pInd=-1:obj.pInd = Math.floor((index-1)/2)
  //     return [...result,obj]
  //   },[])

  /**
   *
   * @param {number} i  i是值发生改变的元素的下标
   * @param {} l l是本次需要重新排序的数组的长度
   * 此方法是对长度为l的数组所组成的大顶堆，在下标为i的节点发生改变之后，从下标为i的元素开始，自顶向下重新排序成大顶堆
   */
  function recursion(i, l) {
    if(i===1)
  debugger
    // 以下代码为比较三个节点，把最大值给到父节点的操作
    
    let temporary = nums[i],
      maxIndex =  i;
    if (i * 2 + 1 > l - 1) return;
    if (nums[i * 2 + 1] > nums[i]) {
      temporary = nums[i * 2 + 1];
      maxIndex = i * 2 + 1;
    }
    if (i * 2 + 2 < l ) {
      if (nums[i * 2 + 2] > temporary) {
        temporary = nums[i * 2 + 2];
        maxIndex = i * 2 + 2;
      }
    }
    if (temporary > nums[i]) {
      nums[maxIndex] = nums[i];
      nums[i] = temporary;
      maxIndex<=Math.floor(l / 2 - 1) && recursion(maxIndex,l);
    }
  }
  // 把堆转换成大顶堆，大顶堆满足V(index)>V(index*2+1),V(index)>V(index*2+2),父节点的值要大于左子节点的值，父节点的值要大于右子节点的值，V函数输入节点下标，输出节点的值
  // 这里采用从堆底，往堆顶的顺序，去调整节点位置，实现所有父节点的值都大于自己的子节点的值，可以采用递归整个树的方式，从根节点代入，从最底层的节点往上算出
  // 从最后 一个非叶子节点开始 ，最后一个非叶子节点下标为index = Math.floor(arr.length/2 - 1) = 1
  const index = Math.floor(nums.length / 2 - 1);
  for (let i = index; i >= 0; i--) {
    recursion(i,nums.length);
  }
  /* 第三步

把最大的值跟数组的最后一个未排序元素交换位置，作为排序好的部分

剩余未排序好的部分继续重复堆排序的过程 */

  // 循环对未排序好的数组部分，执行首尾值互换，重排成大顶堆的操作

  for (let i = nums.length - 1; i > 0; i--) {
 
    // 首尾互换
    let temporary;
    temporary = nums[i];
    nums[i] = nums[0];
    nums[0] = temporary;

    //   重排

    // 再把交換好的数组，进行堆排序，比较根节点跟它的字节点的大小，如果发生交换位置的行为，应该对交换了位置的节点再比较，要把这个过程封装成方法
    recursion(0, i);
  }

  return nums;
};
const result = sortArray([6,10,17,14,19,5,9,10,3,9]);
console.log(result);
